package com.tlvip.arithmetic.ch08;

import java.util.Arrays;

/**
 * <p>description：冒泡排序</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/27/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class PopSort {

    public static void main(String[] args) {
        popSort();
    }

    // 时间复杂度O(n^2)
    // 空间复杂度O(n)
    // 稳定排序
    public static void popSort() {
        int data[] = {4, 5, 6, 3, 2, 1};
        // i < data.length - 1 最后一次留给 j+1
        for (int i = 0; i < data.length - 1; i++) {
            // 是否需要冒泡的标志
            boolean needPopFlag = false;
            // 每次会沉底一个元素，后面的不用遍历比较
            for (int j = 0; j < data.length - 1 - i; j++) {
                // 比较大小并交换相邻两个元素
                if (data[j] > data[j + 1]) {
//                    int temp = data[j + 1];
//                    data[j + 1] = data[j];
//                    data[j] = temp;
                    // 或者另一种写法
                    data[j] = data[j] + data[j + 1];
                    data[j + 1] = data[j] - data[j + 1];
                    data[j] = data[j] - data[j + 1];
                    needPopFlag = true;
                }
            }
            if (!needPopFlag) {
                break;
            }
        }
        System.out.println(Arrays.toString(data));
    }
}
